package com.chj.dfs.class04;

//在 LeetCode 中，「岛屿问题」是一个系列系列问题，比如：
//
//L200. 岛屿数量 （Easy）
//463. 岛屿的周长 （Easy）
//695. 岛屿的最大面积 （Medium）
//827. 最大人工岛 （Hard）

// https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/
public class Code14_NumberOfIslands {
	public static void dfs(char[][] grid, int r, int c) {
		// 判断 base case
		if (!inArea(grid, r, c)) {
			return;
		}
		// 如果这个格子不是岛屿，直接返回
		if (grid[r][c] != '1') {
			return;
		}
		grid[r][c] = '2'; // 将格子标记为「已遍历过」

		// 访问上、下、左、右四个相邻结点
		dfs(grid, r - 1, c);
		dfs(grid, r + 1, c);
		dfs(grid, r, c - 1);
		dfs(grid, r, c + 1);
	}

	// 判断坐标 (r, c) 是否在网格中
	public static boolean inArea(char[][] grid, int r, int c) {
		return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;
	}

	public static int maxAreaOfIsland(char[][] grid) {
		int res = 0;
		for (int r = 0; r < grid.length; r++) {
			for (int c = 0; c < grid[0].length; c++) {
				if (grid[r][c] == '1') {
					dfs(grid, r, c);
					res++;
				}
			}
		}
		return res;
	}

	public static void main(String[] args) {
		char[][] grid1 = { { '1', '1', '1', '1', '0' }, { '1', '1', '0', '1', '0' }, { '1', '1', '0', '0', '0' },
				{ '0', '0', '0', '0', '0' } };
		int numIslands1 = maxAreaOfIsland(grid1);
		System.out.println(numIslands1);

		char[][] grid2 = { { '1', '1', '0', '0', '0' }, { '1', '1', '0', '0', '0' }, { '0', '0', '1', '0', '0' },
				{ '0', '0', '0', '1', '1' } };
		int numIslands2 = maxAreaOfIsland(grid2);
		System.out.println(numIslands2);
	}
}
